package com.ly.algorithm.leetcode.backtracking;

/**
 * @Classname Problem79
 * @Description
 *
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 *  
 *
 * 示例:
 *
 * board =
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 *
 * 给定 word = "ABCCED", 返回 true
 * 给定 word = "SEE", 返回 true
 * 给定 word = "ABCB", 返回 false
 *
 *
 * @Date 2020/12/28 18:41
 * @Author 冷心影翼
 */
public class Problem79 {

	public static void main(String[] args) {
		Solution79 solution79 = new Solution79();
		char[][] board = new char[][] {
			{'A','B','C','E'},
			{'S','F','C','S'},
			{'A','D','E','E'}
		};
		System.out.println(solution79.exist(board, new String("SEE")));
	}
}

class Solution79 {

	public boolean exist(char[][] board, String word) {
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[0].length; j++) {
				boolean backtracking = backtracking(board, word, i, j, 0);
				if(backtracking) {
					return true;
				}
			}
		}
		return false;
	}

	public boolean backtracking(char[][] board,String word,int x,int y,int k) {
		if(k == word.length())
			return true;
		if(x<0 || x>=board.length || y<0 || y>=board[0].length) {
			return false;
		}
		if(board[x][y] != word.charAt(k)) {
			return false;
		}
		char t = board[x][y];

		//右
		board[x][y] = '0';
		if(backtracking(board,word,x,y+1,k+1))
			return true;
		//下
		if(backtracking(board,word,x+1,y,k+1))
			return true;
		//上
		if(backtracking(board,word,x-1,y,k+1))
			return true;
		//左
		if(backtracking(board,word,x,y-1,k+1))
			return true;
		board[x][y] = t;
		return false;
	}
}
